package com.spacewiz13.algorithm.array;

import java.util.HashMap;
import java.util.Map;

/**
 * Given an array of integers, every element appears twice except for one. Find that single one.
	Note:
	Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
	找到数组中只出现一次的数字。时间复杂度为n，尽量不用额外的空间。
 * @author David
 *
 */
public class SingleNumber {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] nums = {1,1,2,2,4,4,5};
		System.out.println(singleNumber2(nums));
	}
	
    public static int singleNumber1(int[] nums) {
    	Map<Integer,Integer> map = new HashMap<Integer,Integer>();
    	for(int num :nums){
    		if(map.get(num) == null){
    			map.put(num,1);
    		}else{
    			int time = map.get(num);
    			map.put(num,time+1);
    		}
    	}
    	for(Map.Entry<Integer,Integer> entry:map.entrySet()){
    		if(entry.getValue() == 1){
    			return entry.getKey();
    		}
    	}
    	return -1;
        
    }
    
    public static int singleNumber2(int[] nums) {
    	int result = 0;
    	for(int num:nums){
    		result = result^num;
    	}
        return result;
    }

}
